#include "LarNumber.h"
#include <iostream>
#include <chrono> // 用于计时
#include <algorithm> // 用于std::reverse
#include <windows.h>

using namespace std;
using namespace chrono;

// 移除前导零的私有方法
void LarNumber::removeLeadingZeros() {
    while (!data.empty() && data.back() == 0) {
        data.pop_back();
    }
}

// 构造函数：从普通整数初始化
LarNumber::LarNumber(uint64_t num) {
    if (num != 0) {
        data.push_back(num);
    }
}

// 大数乘法：当前大数 * 另一个大数，返回新结果
LarNumber LarNumber::multiply(const LarNumber& other) const {
    LarNumber res;
    const auto& a = this->data;
    const auto& b = other.data;
    res.data.resize(a.size() + b.size(), 0); // 结果最多a.size()+b.size()块

    // 分块乘法（模拟竖式，处理进位）
    for (size_t i = 0; i < a.size(); ++i) {
        __uint128_t carry = 0; // 使用128位存储进位
        for (size_t j = 0; j < b.size(); ++j) {
            // 使用128位整数存储中间结果
            __uint128_t product = (__uint128_t)a[i] * b[j] + res.data[i + j] + carry;
            res.data[i + j] = (uint64_t)product; // 取低64位
            carry = product >> 64; // 安全右移64位
        }
        // 处理剩余进位
        size_t k = i + b.size();
        while (carry > 0 && k < res.data.size()) {
            __uint128_t total = (__uint128_t)res.data[k] + carry;
            res.data[k] = (uint64_t)total;
            carry = total >> 64;
            ++k;
        }
    }

    // 移除末尾多余的0（优化存储）
    res.removeLeadingZeros();
    return res;
}

// 重载 *= 运算符（自身 *= 另一个大数）
LarNumber& LarNumber::operator*=(const LarNumber& other) {
    *this = this->multiply(other);
    return *this;
}
    
// 转换为字符串（用于输出结果，小端序转大端序）
std::string LarNumber::toString() const {
    if (data.empty()) return "0";
    string res;
    vector<uint8_t> decimal;
    LarNumber num = *this;
    // 每次取最后一位（10进制），直到num为0
    while (!num.data.empty()) {
        __uint128_t remainder = 0;
        // 大数除以10，余数就是当前最后一位
        for (int i = num.data.size() - 1; i >= 0; --i) {
            __uint128_t value = (__uint128_t)num.data[i] + (remainder << 64);
            num.data[i] = (uint64_t)(value / 10);
            remainder = value % 10;
        }
        
        decimal.push_back((uint8_t)remainder);
        // 移除末尾的0
        num.removeLeadingZeros();
    }
    // 反转字符串（因为取的是低位到高位）
    for (auto it = decimal.rbegin(); it != decimal.rend(); ++it) {
        res.push_back('0' + *it);
    }
    return res;
}

/**
 * C++大数次方计算（快速幂算法）
 * @param base 底数（LarNumber类型）
 * @param exponent 指数（20000）
 * @returns 计算结果（LarNumber类型）
 */
LarNumber LarNumber::bigPowerCPP(const LarNumber& base, int exponent) {
    LarNumber result(1); // 初始结果为1
    LarNumber currentBase = base;
    int currentExponent = exponent;

    // 快速幂核心逻辑（O(log exponent)）
    while (currentExponent > 0) {
        if (currentExponent % 2 == 1) {
            result = result.multiply(currentBase); // 使用赋值操作确保正确累积
        }
        currentBase = currentBase.multiply(currentBase); // 底数平方
        currentExponent /= 2; // 指数折半
    }
    return result;
}

// ... existing code ...

// 分治计算区间乘积的私有方法
LarNumber LarNumber::productRange(int a, int b) {
    if (a > b) return LarNumber(1);
    if (a == b) return LarNumber(a);
    int mid = a + (b - a) / 2;
    LarNumber left = productRange(a, mid);
    LarNumber right = productRange(mid + 1, b);
    return left.multiply(right);
}

// 大数阶乘计算（分治法）
LarNumber LarNumber::bigFactorialCPP(int n) {
    if (n < 0) throw invalid_argument("阶乘参数不能为负数");
    if (n == 0 || n == 1) return LarNumber(1); // 处理0!和1!的情况
    return productRange(1, n);
}

/*
int main() {
    // 设置控制台代码页为UTF-8
    SetConsoleOutputCP(CP_UTF8);
    SetConsoleCP(CP_UTF8);
    // 设置控制台本地化
    setlocale(LC_ALL, "");
    std::locale::global(std::locale(""));
    // 测试：计算 123456^20000
    const uint64_t baseNum = 233456;
    const int exponent = 20000;
    LarNumber base(baseNum);

    // 计时开始
    auto start = high_resolution_clock::now();
    LarNumber cppResult = LarNumber::bigPowerCPP(base, exponent);
    // 计时结束
    auto end = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(end - start);

    // 输出结果
    cout << "C++ 计算耗时：" << duration.count() << " 毫秒" << endl;
    string resultStr = cppResult.toString();
    cout << "结果：" << resultStr << endl;
    // 等待用户输入任意键退出
    cout << "Press any key to exit..." << endl;
    cin.get();
    return 0;
}
*/